﻿using System;
using System.Collections.Generic;

namespace NetTopologySuite.Planargraph.Algorithm
{
	public class ConnectedSubgraphFinder
	{
		public ConnectedSubgraphFinder(PlanarGraph graph)
		{
			this.graph = graph;
		}

		public IList<Subgraph> GetConnectedSubgraphs()
		{
			IList<Subgraph> list = new List<Subgraph>();
			GraphComponent.SetVisited(this.graph.GetNodeEnumerator(), false);
			IEnumerator<Edge> edgeEnumerator = this.graph.GetEdgeEnumerator();
			while (edgeEnumerator.MoveNext())
			{
				Edge edge = edgeEnumerator.Current;
				Node fromNode = edge.GetDirEdge(0).FromNode;
				if (!fromNode.IsVisited)
				{
					list.Add(this.FindSubgraph(fromNode));
				}
			}
			return list;
		}

		private Subgraph FindSubgraph(Node node)
		{
			Subgraph subgraph = new Subgraph(this.graph);
			this.AddReachable(node, subgraph);
			return subgraph;
		}

		private void AddReachable(Node startNode, Subgraph subgraph)
		{
			Stack<Node> stack = new Stack<Node>();
			stack.Push(startNode);
			while (stack.Count != 0)
			{
				ConnectedSubgraphFinder.AddEdges(stack.Pop(), stack, subgraph);
			}
		}

		private static void AddEdges(Node node, Stack<Node> nodeStack, Subgraph subgraph)
		{
			node.Visited = true;
			foreach (DirectedEdge directedEdge in node.OutEdges)
			{
				subgraph.Add(directedEdge.Edge);
				Node toNode = directedEdge.ToNode;
				if (!toNode.IsVisited)
				{
					nodeStack.Push(toNode);
				}
			}
		}

		private readonly PlanarGraph graph;
	}
}
